In the above technical field, non-patent literature 1 discloses a technique of comparing the magnitudes of encrypted numerical values as follows. When a numerical value M as a plaintext and a key K are provided, a ciphertext C is generated as C=Enc(K, M) using an encryption function Enc. At this time, with respect to two arbitrary numbers M and M′ satisfying M>M′, Enc(K, M)>Enc(K, M′) holds. That is, when C=Enc(K, M) and C′=Enc(K, M′), the magnitude relationship between the numerical values M and M′ can be known without decrypting the ciphertexts C and C′.
Non-patent literature 2 discloses a technique of comparing the magnitudes of encrypted numerical values as follows. Non-patent literature 2 is a kind of common key cryptography in which a document M as a plaintext divided into a plurality of blocks like M=(b[1], . . . , b[n]) is encrypted to generate a ciphertext of a plurality of blocks like C=(c[1], . . . , c[n]). If two plaintexts match each other with respect to the first k blocks, their ciphertexts also match each other with respect to the first k blocks. This method can thus determine that the plaintexts partially match each other in a ciphertext form.